class Permutation:
    def __init__(self, mod=10 ** 9 + 7):
        self._mod = mod
        self._size = 0

        self._factorial = [1]  # 阶乘缓存列表 : self.fact[i] = i!
        self._factorial_inv = [1]  # 阶乘的乘法逆元缓存列表

    def factorial(self, n):
        """计算阶乘"""
        if n > self._size:
            for i in range(self._size + 1, n + 1):
                self._factorial.append((self._factorial[-1] * i) % self._mod)
                self._factorial_inv.append(pow(self._factorial[-1], self._mod - 2, self._mod))
            self._size = n
        return self._factorial[n]

    def arrange(self, n, m):
        """排列数公式"""
        return self.factorial(n) // self.factorial(n - m)

    def comb(self, n, m):
        """组合数公式"""
        return self.arrange(n, m) // self.factorial(m)


class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        return n - self.count(n)

    def count(self, n: int) -> int:  # 小于等于n的  没有重复digit的num 的 个数
        """计算有多少个没有重复数字的小于等于n的数"""
        permutation = Permutation()  # 初始化排列数计算器

        digits = [int(i) for i in str(n)]
        size = len(digits)

        ans = 0

        # 处理不同数量的0开头的情况
        for i in range(1, size):
            ans += 9 * permutation.arrange(9, i - 1)  # 首尾有9种选择，后面是9种选择（0-9去掉首尾的数字）的

        # 当前每个数的出现次数
        visited = [0] * 10

        # 处理非0开头的情况
        for i in range(size):
            min_digit = 1 if i == 0 else 0  # 当前位可选最小值（第0位时不能选择0）
            max_digit = digits[i]  # 当前位可选最大值

            # 先遍历的当前位最大值之前的数字
            for x in range(min_digit, max_digit):
                if visited[x] == 0:  # 如果当前位还没有被用过
                    ans += permutation.arrange(10 - i - 1, size - i - 1)

            # 处理当前位最大值的情况
            visited[max_digit] += 1
            if visited[max_digit] > 1:  # 如果已经重复则放弃
                break

            # 如果到达最后一位，那么本身也是符合条件的
            if i == size - 1:
                ans += 1
                
        return ans


if __name__ == "__main__":
    print(Solution().numDupDigitsAtMostN(20))  # 1
    print(Solution().numDupDigitsAtMostN(100))  # 10
    print(Solution().numDupDigitsAtMostN(121))  # 22
    print(Solution().numDupDigitsAtMostN(1000))  # 262

    # 测试用例62/129
    print(Solution().numDupDigitsAtMostN(1))  # 0

    # 测试用例63/129
    print(Solution().numDupDigitsAtMostN(9))  # 0

    # 测试用例64/129
    print(Solution().numDupDigitsAtMostN(110))  # 12

    # 测试用例69/129
    print(Solution().numDupDigitsAtMostN(1962))  # 739
